Built with
Offline Website CreatorA system for the procedural generation of Sokoban puzzles that was researched, designed and developed for my final-year dissertation project for BSc Games Technology.
The system is a procedural content generation system capable of generating unique Sokoban puzzles as part of a larger maze level structure. The system ensures that the generated puzzles are always solvable and and of a suitable complexity. The produced puzzles are also generated within a reasonable amount of time.
The system makes use of a number of different algorithms to generate the resulting Sokoban puzzles.
The generated puzzles and maze layouts can be adjusted by modifying parameters using a GUI which affects how the algorithms are run.
The system makes use of a number of different algorithms to generate the resulting Sokoban puzzles. Which combined together is capable of producing Sokoban puzzle in a range of sizes as part of a larger procedurally generated maze.
Room Generation
The first step for generating unique Sokoban levels is the generation of empty rooms which creates the layout that will contain the puzzle.
The empty rooms are generated by combining predefined layout templates together.
Puzzle Generation
The puzzles are generated using a backtracking algorithm. The algorithm makes use of to find the best possible solution for the current room layout.
The system first starts in the solved state and works backwards in order to find the most complex possible solution for the current room layout.
The most complex state is found by finding all possible moves from each state, then sort all states in order of depth. Once all possible moves are attempted, the state with the highest depth value is chosen.
Maze Generation
The approach taken was to generate a maze layout with a depth first search algorithm, then incorporate Sokoban levels as each cell of the maze layout.
Room Size: The width and the height of the resulting puzzle rooms can be adjusted. This affects the number of template tiles which are combined together. The number of boxes within the rooms are determined by the scale of the room - meaning the difficulty of the resulting puzzles are determined by the scale of the room.
Maze Size: The maximum width and height of the maze layout in which the generated puzzles are laid out.
Built with
Offline Website Creator